package com.zhangxiaofanfan.hotcode.third;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked">最长连续序列</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-05-21 08:17:51
 */
public class HotCode003 {
    public static void main(String[] args) {
        int[] nums = {100,4,200,1,3,2};
        HotCode003 hotCode003 = new HotCode003();
        System.out.println(hotCode003.longestConsecutive(nums));

        // 输入：nums = [0,3,7,2,5,8,4,6,0,1]
    }

    public int longestConsecutive(int[] nums) {
        Map<Integer, Deque<Integer>> mapFront = new HashMap<>();
        Map<Integer, Deque<Integer>> mapBack = new HashMap<>();
        for (int num : nums) {
            if (!mapFront.containsKey(num) && !mapBack.containsKey(num)) {
                Deque<Integer> deque = new ArrayDeque<>();
                deque.addLast(num);
                mapFront.put(num - 1, deque);
                mapBack.put(num + 1, deque);
            } else if (mapFront.containsKey(num) && !mapBack.containsKey(num)) {
                Deque<Integer> deque = mapFront.remove(num);
                deque.addFirst(num);
                mapFront.put(num - 1, deque);
            } else if (!mapFront.containsKey(num) && mapBack.containsKey(num)) {
                Deque<Integer> deque = mapBack.remove(num);
                deque.addLast(num);
                mapBack.put(num + 1, deque);
            } else {
                Deque<Integer> deque2 = mapFront.remove(num);
                Deque<Integer> deque1 = mapBack.remove(num);
                deque1.addLast(num);
                deque1.addAll(deque2);
                mapFront.put(deque1.getFirst() - 1, deque1);
                mapBack.put(deque1.getLast() + 1, deque1);
            }
        }
        return mapFront.values().stream().max(Comparator.comparingInt(Deque::size)).get().size();
    }
}
